function HeapQueue() {
    
}

// 堆调整方法，调整为大顶堆
HeapQueue.prototype.heapAdjust = function (arr, index, end) {
    let left = index * 2 + 1
    let right = left + 1
    while (left <= end) {
        let maxIndex = index
        if (arr[left] > arr[maxIndex]) {
            maxIndex = left
        }
        if (right <= end && arr[right] > arr[maxIndex]) {
            maxIndex = right
        }
        if (index === maxIndex) {
            // 不需要交换，交换结束
            break
        }
        [arr[index], arr[maxIndex]] = [arr[maxIndex], arr[index]]
        // 继续调整子树
        index = maxIndex
        left = index * 2 + 1
        right = left + 1
    }
}

// 将数组构建为二叉堆
HeapQueue.prototype.heapify = function (arr) {
    for (let i = Math.floor(arr.length / 2); i >= 0 ; i--) {
        this.heapAdjust(arr, i, arr.length - 1)
    }
}

// 入队操作
HeapQueue.prototype.heappush = function (arr, value) {
    arr.push(value)
    let size = arr.length
    let i = size - 1
    while (Math.floor((i - 1) / 2 >= 0)) {
        let curRoot = Math.floor((i - 1) / 2) 
        // 如果value小于当前根节点，则插入到当前位置
        if (arr[curRoot] > value) {
            break
        }
        // 继续向上查找
        arr[i] = arr[curRoot]
        i = curRoot
    }
    arr[i] = value
}

// 出队操作
HeapQueue.prototype.heappop = function (arr) {
    let size = arr.length;
    [arr[0], arr[size - 1]] = [arr[size - 1], arr[0]];
    // 得到最大值然后调整堆
    let top = arr.pop()
    if (size > 0) {
        this.heapAdjust(arr, 0, size -2)
    }
    return top
}

// 升序堆排序
HeapQueue.prototype.heapSort = function (arr) {
    this.heapify(arr)
    let size = arr.length
    for (let i = 0; i < arr.length; i++) {
        [arr[0], arr[size - i - 1]] = [arr[size - i - 1], arr[0]]
        this.heapAdjust(arr, 0, size - i - 2)
    }
    return arr
}

// let arr = [2, 4, 1, 8, 5, 7, 9, 4, 6]
// let queue = new HeapQueue()
// console.log(queue.heapSort(arr))
// queue.heappush(arr, 10)
// console.log(arr);

module.exports = {
    HeapQueue
}